package trie;

import java.util.TreeMap;

/**
 * @program: play-structure
 * @author: baichen
 * 力扣211：设计一个支持以下两种操作的数据结构：
 * void addWord(word)
 * bool search(word)
 * search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
 * 有点类似正则表达式
 **/
public class WordDictionary {
    private class Node {
        public boolean isWord;      //判断当前的节点是否代表一个单词的结尾
        // 到下一个节点的映射，字符串是Character,可以根据实际情况替换为别的数据类型
        // 从Character到Node，从字符映射到节点
        public TreeMap<Character, Node> next;

        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);    //大多数当前节点都不是单词结尾
        }
    }

    private Node root;

    /**
     * Initialize your data structure here.
     */
    public WordDictionary() {
        root = new Node();
    }

    /**
     * Adds a word into the data structure.
     */
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            //这里是使用了映射，字符映射到节点，所以根据字符查找这个节点是否存在
            //如果为空(即不存在)则存入这个字符并新建一个节点
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            //如果存在则直接指向这个节点，新增这个字符对应的节点
            cur = cur.next.get(c);
        }
        //不添加重复的单词
        if (!cur.isWord) {  //该节点不是任何单词的结尾,即添加的单词不存在
            cur.isWord = true;
        }
    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        //从根结点，字符串word的第一个字符开始
        return match(root, word, 0);
    }

    /**
     * 对于.，要递归遍历所有的可能
     *
     * @param node  以node为根开始搜索
     * @param word  要搜索的单词
     * @param index 字符串的index对应的字符搜索
     * @return 是否包含这个word
     */
    private boolean match(Node node, String word, int index) {
        //递归到底的情况
        if (index == word.length()) {
            return node.isWord;
        }
        char c = word.charAt(index);
        if (c != '.') { //c是具体字符，先判断其对应的节点是否存在，不存在就直接返回空
            if (node.next.get(c) == null) {
                return false;
            }
            //如果存在则开始递归，然后index要加一
            return match(node.next.get(c), word, index + 1);
        } else { //如果c对应的是'.'，遍历所有的可能,key就是字符
            for (char nextChar : node.next.keySet()) {
                //跳过'.'，匹配所有的key，即字符，如果匹配得上，则返回true
                if (match(node.next.get(nextChar), word, index + 1)) {
                    return true;
                }
            }
            //所有的key都没有匹配上，返回false
            return false;
        }
    }

    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */
}
